import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int array[] = {6,1,2,7,9,3,4,5,10,8};
        int temp[] = new int[array.length];
        mergeSort(array,0,array.length - 1, temp);
        System.out.println(Arrays.toString(array));

    }

    /**
     * 将数组拆分成单个元素，每次从中间分割
     * @param array:待排序的数组
     * @param left:左指针
     * @param right:右指针
     * @param temp:暂存的数组元素
     */
    public static void mergeSort(int[] array,int left,int right,int[] temp){
        if(left < right){
            int mid = (left + right) / 2;
            mergeSort(array,left,mid,temp);
            mergeSort(array,mid + 1,right,temp);
            merge(array,left,mid,right,temp);
        }
    }

    /**
     * 归并方法
     * @param array:待排序的数组
     * @param left:左指针
     * @param mid:中指针
     * @param right:右指针
     * @param temp:暂存的数组元素
     */
    public static void merge(int[] array,int left,int mid, int right,int[] temp){
        int i = left;
        int j = mid + 1;
        int t = 0;

        //当左边未到基准指针以及右边未到右指针
        while(i <= mid && j <= right){
            if(array[i] <= array[j]){
                temp[t] = array[i];
                i++;
                t++;
            }else{
                temp[t] = array[j];
                t++;
                j++;
            }
        }

        //将左边剩余的元素存入暂存数组
        while(i <= mid){
            temp[t] = array[i];
            t++;
            i++;
        }

        //将右边剩余的元素存入暂存数组
        while(j <= right){
            temp[t] = array[j];
            t++;
            j++;
        }

        t = 0;
        int templeft = left;
        while(templeft <= right){
            array[templeft] = temp[t];
            t++;
            templeft++;
        }

    }
}
